1. Field of the Invention
The present invention relates to computer systems and methods in which data resources are shared among concurrent data consumers while preserving data integrity and consistency relative to each consumer. More particularly, the invention concerns an implementation of a mutual exclusion mechanism known as “reader-writer synchronization.”
2. Description of the Prior Art
By way of background, reader-writer synchronization, also known as “reader-writer locking,” is a mutual exclusion technique that is suitable for use in shared memory multiprocessor computing environments to protect a set of shared data. This form of locking allows read operations (readers) to share lock access in order to facilitate parallel data reads, but requires write operations (writers) to obtain exclusive lock access for writing the data. The technique is well suited to shared memory multiprocessor computing environments in which the number of readers accessing a shared data set is large in comparison to the number of writers, and wherein the overhead cost of requiring serialized lock acquisition for readers would be high. For example, a network routing table that is updated at most once every few minutes but searched many thousands of times per second is a case where serialized read-side locking would be quite burdensome.
Reader-writer locks are conventionally implemented using either a single global lock that is shared among processors, or as a set of distributed per-processor locks. The global reader-writer lock approach is illustrated in FIG. 1. It requires readers and writers to contend for one global lock on an equal footing, but produces memory contention delays due to cache line bouncing of the lock between each processor's cache. Insofar as reader-writer locks are premised on the existence of a read-intensive processing environment, readers may be unduly penalized, especially if their critical sections are short and their lock acquisition frequency is high. The distributed reader-writer lock approach is illustrated in FIG. 2. It requires the readers to acquire only a local per-processor lock that will usually reside in the memory cache of the processor that hosts the acquiring reader. However, the writers must acquire all of the local locks, which degrades writer performance due to memory contention and in some cases due to new readers being allowed to starve a writer while the latter is waiting for one of the local locks.
A further disadvantage associated with either type of reader-writer locking is that lock acquisition imposes a burden on readers, even in the absence of a writer. Reader-writer locks are typically implemented as semaphores, mutex locks and spinlocks. Acquiring each of these lock types often imposes the cost of atomic instructions and/or memory barriers. In a read-mostly computing environment, the overhead associated with these operations falls mostly on readers.
It is to solving the foregoing problems that the present invention is directed. In particular, what is required is a reader-writer locking technique that is fair to writers yet which reduces the overhead associated with read-side lock acquisition.